from typing import Optional, List, Counter


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    # [147. 对链表进行插入排序](https://leetcode.cn/problems/insertion-sort-list/submissions/619177305/?envType=problem-list-v2&envId=sorting)
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 创建一个新链表存储排序后的节点
        sort_list = ListNode(0)

        cur = head
        while cur != None:
            prev = sort_list # 用于比较新链表的节点值
            cur_next = cur.next

            # 查找插入位置
            while prev.next and prev.next.val < cur.val:
                prev = prev.next

            # 插入节点
            cur.next = prev.next
            prev.next = cur

            # 继续步骤
            cur = cur_next

        return sort_list.next

    # (148. 排序链表)[https://leetcode.cn/problems/sort-list/?envType=problem-list-v2&envId=sorting]
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 基本情况: 链表为空或只有一个元素
        if not head or not head.next:
            return head

        # 辅助函数: 分割链表
        def split(head):
            slow = fast = head
            prev = None
            while fast and fast.next:
                prev = slow
                slow = slow.next
                fast = fast.next.next

            # 将链表从中间断开
            prev.next = None
            return head, slow

        # 辅助函数: 合并链表
        def merge(left, right):
            new_head = ListNode(0)  # 哨兵节点
            cur = new_head

            # 合并两个已排序的链表
            while left and right:
                if left.val < right.val:
                    cur.next = left
                    left = left.next
                else:
                    cur.next = right
                    right = right.next
                cur = cur.next

            # 将剩余的链表连接到合并后的链表
            if left:
                cur.next = left
            elif right:
                cur.next = right

            return new_head.next

        # 分割链表
        left, right = split(head)

        # 递归地排序链表
        left = self.sortList(left)
        right = self.sortList(right)

        # 合并已排序的左右链表
        return merge(left, right)

    # (164. 最大间距)[https://leetcode.cn/problems/maximum-gap/description/?envType=problem-list-v2&envId=sorting]
    def maximumGap(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return 0

        # 1. 找到数组中的最小值和最大值
        min_val = min(nums)
        max_val = max(nums)

        # 2. 计算桶的大小和桶的数量
        bucket_size = max(1, (max_val - min_val) // (len(nums) - 1))  # 防止桶大小为0
        bucket_count = (max_val - min_val) // bucket_size + 1

        # 3. 创建桶，桶内记录 (min, max) 值
        buckets = [[float('inf'), float('-inf')] for _ in range(bucket_count)]

        # 4. 将元素放入对应的桶中
        for num in nums:
            idx = (num - min_val) // bucket_size  # 找到元素属于哪个桶
            buckets[idx][0] = min(buckets[idx][0], num)  # 更新桶的最小值
            buckets[idx][1] = max(buckets[idx][1], num)  # 更新桶的最大值

        # 5. 计算最大差值
        max_gap = 0
        prev_max = min_val  # 上一个非空桶的最大值

        for i in range(bucket_count):
            if buckets[i][0] == float('inf'):  # 这个桶为空，跳过
                continue
            # 当前桶的最小值减去前一个桶的最大值
            max_gap = max(max_gap, buckets[i][0] - prev_max)
            prev_max = buckets[i][1]  # 更新前一个桶的最大值

        return max_gap

    # (937. 重新排列日志文件)[https://leetcode.cn/problems/reorder-data-in-log-files/description/?envType=problem-list-v2&envId=sorting]
    def reorderLogFiles1(self, logs: List[str]) -> List[str]:
        digit_list, letter_list = [], []

        # 统计字母日志与数字日志
        for log in logs:
            if log.split()[1].isdigit():
                digit_list.append(log)
            else:
                letter_list.append(log)

        # 排序字母日志
        # 如果内容（字母）部分不同，按照字母部分排序，相同则按照标识符排序
        letter_list.sort(key=lambda x: (x.split()[1:], x.split()[0]))

        return letter_list + digit_list

    def reorderLogFiles2(self, logs: List[str]) -> List[str]:
        digit_list, letter_list = [], []

        for log in logs:
            if log.split()[1].isdigit():
                digit_list.append(log)
            else:
                letter_list.append(log)

        # 辅助函数: 快排
        def quickSort(arr):
            if len(arr) <= 1:
                return arr

            left_arr, equal_arr, right_arr = [], [], []
            pivot = arr[0]
            for log in arr:
                if (log.split()[1:], log.split()[0]) < (pivot.split()[1:], pivot.split()[0]):
                    left_arr.append(log)
                elif (log.split()[1:], log.split()[0]) > (pivot.split()[1:], pivot.split()[0]):
                    right_arr.append(log)
                else:
                    equal_arr.append(log)

            return quickSort(left_arr) + equal_arr + quickSort(right_arr)

        letter_list = quickSort(letter_list)
        return letter_list + digit_list

    # (1030. 距离顺序排列矩阵单元格)[https://leetcode.cn/problems/matrix-cells-in-distance-order/description/?envType=problem-list-v2&envId=sorting]
    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:
        cells = []

        for r in range(rows):
            for c in range(cols):
                distance = abs(r - rCenter) + abs(c - cCenter)
                cells.append([r, c, distance])

        cells.sort(key=lambda x: x[2]) # 按照第三个元素（距离）排序

        return [[cell[0], cell[1]] for cell in cells]

    # (1122. 数组的相对排序)[https://leetcode.cn/problems/relative-sort-array/description/?envType=problem-list-v2&envId=sorting]\
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        count = Counter[arr1]  # 获取arr1中每个元素的出现次数

        ret = []  # 结果数组
        for num in arr2:
            ret.extend([num] * count[num])
            count[num] = 0  # 处理过的元素次数设为0

        remain = []  # arr2中没有的元素
        for num, freq in count.items():
            if freq > 0:
                remain.extend([num] * freq)

        remain.sort()

        return ret + remain

    # (15. 三数之和)[https://leetcode.cn/problems/3sum/description/?envType=problem-list-v2&envId=sorting]
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()  # 排序数组

        ret = list()

        for first in range(n):  # for循环固定第一位
            if first > 0 and nums[first] == nums[first - 1]:  # 跳过重复的
                continue

            target = -nums[first]
            third = n - 1  # 第三位从后计算

            for second in range(first + 1, n):
                if second > first + 1 and nums[second] == nums[second - 1]:  #
                    continue

                while second < third and nums[second] + nums[third] > target:
                    third -= 1

                if second == third:  # b, c相遇，此次循环不会有额外结果
                    break

                if nums[second] + nums[third] == target:
                    ret.append([nums[first], nums[second], nums[third]])

        return ret

    # (16. 最接近的三数之和)[https://leetcode.cn/problems/3sum-closest/description/?envType=problem-list-v2&envId=sorting]
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        # 先排序数组
        nums.sort()
        best = 1e7
        n = len(nums)

        # 内置辅助函数，更新最接近的值
        def update(cur):
            nonlocal best
            if abs(cur - target) < abs(best - target):
                best = cur

        for i in range(n):
            if i > 0 and nums[i] == nums[i - 1]:  # 跳过重复的
                continue

            j, k = i + 1, n - 1
            while j < k:
                total = nums[i] + nums[j] + nums[k]
                if total == target:
                    return total
                elif total > target:
                    k_temp = k
                    while k_temp > j and nums[k_temp] == nums[k]:
                        k_temp -= 1
                    k = k_temp
                else:
                    j_temp = j
                    while j_temp < k + 1 and nums[j_temp] == nums[j]:
                        j_temp += 1
                    j = j_temp

                update(total)

        return 0 if best == 1e7 else best

    # (18. 四数之和)[https://leetcode.cn/problems/4sum/description/?envType=problem-list-v2&envId=sorting]
    class Solution:
        def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
            result = list()
            n = len(nums)
            nums.sort()

            for i in range(n - 3):
                if i > 0 and nums[i] == nums[i - 1]:  # 去重
                    continue
                # 剪枝
                if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target:  # 当循环的最小的四数和都更大时，跳出（i只能向右移动）
                    break
                if nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target:  # 当此次循环最大和都更小时，直接下一层循环
                    continue

                for j in range(i + 1, n - 2):
                    if j > i + 1 and nums[j] == nums[j - 1]:  # 去重
                        continue
                    # 剪枝
                    if nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target:
                        break
                    if nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target:
                        continue

                    k, l = j + 1, n - 1
                    while k < l:
                        total = nums[i] + nums[j] + nums[k] + nums[l]  # 计算总和
                        if total == target:
                            result.append([nums[i], nums[j], nums[k], nums[l]])
                            while l > k and nums[l] == nums[l - 1]:
                                l -= 1
                            l -= 1
                            while k < l and nums[k] == nums[k + 1]:
                                k += 1
                            k += 1
                        elif total > target:
                            l -= 1
                        else:
                            k += 1

            return result

    # (46. 全排列)[https://leetcode.cn/problems/permutations/description/]
    def permute(self, nums: List[int]) -> List[List[int]]:
        path = []
        ret = []
        n = len(nums)
        used = [False] * n

        def dfs():
            if len(path) == n:
                ret.append(path[:])  # 深拷贝
                return

            for i in range(n):
                if not used[i]:
                    used[i] = True
                    path.append(nums[i])
                    dfs()
                    path.pop()  # 回溯
                    used[i] = False

        dfs()
        return ret

    # (229. 多数元素 II)[https://leetcode.cn/problems/majority-element-ii/description/?envType=problem-list-v2&envId=sorting]
    def majorityElement1(self, nums: List[int]) -> List[int]:
        n = len(nums)
        n = n // 3
        count = Counter(nums)
        ret = []
        for value, freq in count.items():
            if freq > n:
                ret.append(value)

        return ret

    def majorityElement2(self, nums: List[int]) -> List[int]:
        # 由于要找的元素出现次数最多为 [n / 3]，则数组中最多两个多数元素
        # 第一遍：找出可能的候选者
        candidate1, candidate2, count1, count2 = None, None, 0, 0

        for num in nums:
            if num == candidate1:
                count1 += 1
            elif num == candidate2:
                count2 += 1
            elif count1 == 0:
                candidate1, count1 = num, 1
            elif count2 == 0:
                candidate2, count2 = num, 1
            else:
                (count1, count2) = (count1 - 1, count2 - 1)

        # 第二遍: 判断候选者出现次数是否超过n/3
        count1, count2 = 0, 0
        for num in nums:
            if num == candidate1:
                count1 += 1
            if num == candidate2:
                count2 += 1

        # 获取结果
        ret = []
        if count1 > len(nums) // 3:
            ret.append(candidate1)
        if count2 > len(nums) // 3:
            ret.append(candidate2)

        return ret

    # (220. 存在重复元素 III)[https://leetcode.cn/problems/contains-duplicate-iii/description/?envType=problem-list-v2&envId=sorting]
    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
        if indexDiff <= 0 or valueDiff < 0 or not nums:
            return False

        width = valueDiff + 1  # 每个桶的大小是 valueDiff + 1
        buckets = {}  # 存储桶，key为桶的索引，value为桶中的值

        # 用来映射数字对应的桶的索引
        def getBucketKey(num, width):
            return (num - 1) // width

        for i in range(len(nums)):
            # 窗口大小超出indexDiff，删除最前面的
            if i > indexDiff:
                del buckets[getBucketKey(nums[i - indexDiff - 1], width)]

            # 当前元素
            num = nums[i]
            curKey = getBucketKey(num, width)

            # 当前桶内已经有内容
            if curKey in buckets:
                return True
            # 检查相邻桶
            if curKey - 1 in buckets and num - buckets[curKey - 1] < width:
                return True
            if curKey + 1 in buckets and buckets[curKey + 1] - num < width:
                return True

            buckets[curKey] = num

        return False

    # (274. H 指数)[https://leetcode.cn/problems/h-index/description/?envType=problem-list-v2&envId=sorting]
    def hIndex(self, citations: List[int]) -> int:
        citations.sort()

        i, h = len(citations) - 1, 0
        # 从大到小遍历
        while i >= 0 and citations[i] > h:
            h += 1
            i -= 1

        return h

    # (910. 最小差值 II)[https://leetcode.cn/problems/smallest-range-ii/description/?envType=problem-list-v2&envId=sorting]
    def smallestRangeII(self, nums: List[int], k: int) -> int:
        nums.sort()  # 先对数组进行排序

        # 初始情况下，最大值和最小值的差值
        initial_range = nums[-1] - nums[0]

        # 对数组进行调整的策略：
        # 最大值变成 nums[-1] - k，最小值变成 nums[0] + k，或者
        # 最大值变成 nums[-1] + k，最小值变成 nums[0] - k。

        # 我们尝试把最小值变大，最大值变小，或者反过来。
        result = initial_range  # 默认最小分数就是不变的情况

        for i in range(1, len(nums)):  # i是分界点
            max_val = max(nums[-1] - k, nums[i - 1] + k)  # 最大值可能会是 nums[i-1] + k 或 nums[-1] - k
            min_val = min(nums[0] + k, nums[i] - k)  # 最小值可能会是 nums[i] - k 或 nums[0] + k
            result = min(result, max_val - min_val)  # 更新最小的分数

        return result

    # (969. 煎饼排序)[https://leetcode.cn/problems/pancake-sorting/submissions/621147293/?envType=problem-list-v2&envId=sorting]
    def pancakeSort(self, arr: List[int]) -> List[int]:
        ret = []
        for n in range(len(arr), 1, -1):
            index = 0
            for i in range(n):
                if arr[i] > arr[index]:  # 找当前数组最大值的下标
                    index = i

            if index == n - 1: continue  # 如果最大值已经在最后，跳过此次

            m = index
            for i in range((m + 1) // 2):  # 反转到index
                arr[i], arr[m - i] = arr[m - i], arr[i]
            for i in range(n // 2):
                arr[i], arr[n - 1 - i] = arr[n - 1 - i], arr[i]  # 原地反转
            ret.append(index + 1)
            ret.append(n)

        return ret

    # (最接近原点的 K 个点)[https://leetcode.cn/problems/k-closest-points-to-origin/description/?envType=problem-list-v2&envId=sorting]
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        # 计算欧几里得距离
        def getEuclidPath(x1, y1):
            return x1 ** 2 + y1 ** 2  # 只需要平方值，避免计算sqrt，性能更好

        # 创建一个列表存储每个点及其距离
        distance_points = []

        for x, y in points:
            distance = getEuclidPath(x, y)
            distance_points.append((distance, [x, y]))  # 距离和点作为元组

        # 按距离排序
        distance_points.sort(key=lambda x: x[0])

        # 返回前 k 个点
        return [point[1] for point in distance_points[:k]]

    # (1122. 数组的相对排序)[https://leetcode.cn/problems/relative-sort-array/description/?envType=problem-list-v2&envId=sorting]
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        count1 = Counter(arr1)
        ret = []
        for i in arr2:  # 统计在arr2中出现过的元素
            if i in arr1:
                ret.extend([i] * count1[i])
                count1[i] = 0

        remaining = []
        for value, freq in count1.items():  # 统计未出现在arr2中的元素
            if freq > 0:
                remaining.extend([value] * freq)

        # 未出现的部分按升序排序
        remaining.sort()

        return ret + remaining

    # (1337. 矩阵中战斗力最弱的 K 行)[https://leetcode.cn/problems/the-k-weakest-rows-in-a-matrix/description/?envType=problem-list-v2&envId=sorting]
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        # 计算每行的军人数量，并将其和对应的行索引存入一个列表
        strength = []
        for i, row in enumerate(mat):
            # 计算当前行的军人数量
            soldiers_count = row.count(1)
            strength.append((soldiers_count, i))

        # 按照军人数量（第一个元素）排序，如果数量相同，按索引（第二个元素）排序
        strength.sort(key=lambda x: (x[0], x[1]))

        # 提取前 k 个最弱行的索引
        return [x[1] for x in strength[:k]]

    # (1460. 通过翻转子数组使两个数组相等)[https://leetcode.cn/problems/make-two-arrays-equal-by-reversing-subarrays/description/?envType=problem-list-v2&envId=sorting]
    def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
        target.sort()
        arr.sort()

        return target == arr

    # (1637. 两点之间不包含任何点的最宽垂直区域)[https://leetcode.cn/problems/widest-vertical-area-between-two-points-containing-no-points/description/?envType=problem-list-v2&envId=sorting]
    def maxWidthOfVerticalArea(self, points: List[List[int]]) -> int:
        points.sort(key=lambda x: x[0]) # 以x坐标为基准排序

        max_width = 0
        for i in range(1, len(points)):
            max_width = max(max_width, points[i][0] - points[i-1][0])

        return max_width

    # (893. 特殊等价字符串组)[https://leetcode.cn/problems/groups-of-special-equivalent-strings/description/?envType=problem-list-v2&envId=sorting]
    def numSpecialEquivGroups(self, words: List[str]) -> int:
        unique_groups = set() # 存放每个字符串的标准化形式

        for word in words:
            even_chars = sorted(word[::2]) # 偶数索引字符
            odd_chars = sorted(word[1::2]) # 奇数索引字符

            # 将偶数和奇数索引排序后的字符组合成一个元组作为唯一标识
            # ['a', 'b', 'c', 'd'] -> (['a', 'c'], ['b', 'd'])
            unique_groups.add((tuple(even_chars), tuple(odd_chars)))

        return len(unique_groups)

    # (869. 重新排序得到 2 的幂)[https://leetcode.cn/problems/reordered-power-of-2/?envType=problem-list-v2&envId=sorting]
    def reorderedPowerOf2(self, n: int) -> bool:
        # 2的幂的二进制只有一个1
        n_count = Counter(str(n))

        power_of_two = 1
        for _ in range(32):
            if Counter(str(power_of_two)) == n_count:
                return True
            power_of_two *= 2

        return False

    # (1094. 拼车)[https://leetcode.cn/problems/car-pooling/description/?envType=problem-list-v2&envId=sorting]
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        diff = [0] * 1001 # 差分数组
        # 计算每个上车下车点的加减乘客数量
        for numPassengersi, fromi, toi in trips:
            diff[fromi] += numPassengersi
            diff[toi] -= numPassengersi

        cur_passengers = 0
        for passenger in diff:
            cur_passengers += passenger
            if cur_passengers > capacity:
                return False

        return True